package 合并二叉树;

public class Solution {
    /*
    给你两棵二叉树： root1 和 root2 。
    想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。
    你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；
    否则，不为 null 的节点将直接作为新二叉树的节点。
    返回合并后的二叉树。
    注意: 合并过程必须从两个树的根节点开始。
     */
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        // 递归
        // 递归的参数：两棵树
        // 递归的返回值：根节点
        // 递归的终止条件：有任何一棵树为null时
        // 单层递归逻辑：同时从两个树的根节点进行遍历，当两颗树都存在当前遍历节点时，只需要将值进行相加
        // 当一个树存在节点，一棵树不存在，那么就需要将存在节点的子树全部加到新树中
        // 当两颗树都不存在节点时，返回null

        if(root1 == null && root2 == null){
            return null;
        } else if (root1 == null) {
            // 将root2的子树加入到新树中
            return buildSubTree(root2);
        }else if (root2 == null){
            // 将root1的子树加入到新树中
            return buildSubTree(root1);
        }

        // 合并为新节点
        TreeNode root = new TreeNode(root1.val + root2.val);
        // 构建左子树
        root.left = mergeTrees(root1.left, root2.left);
        // 构建右子树
        root.right = mergeTrees(root1.right, root2.right);

        return root;
    }

    public TreeNode buildSubTree(TreeNode root){
        if(root == null){
            return null;
        }
        TreeNode node = new TreeNode(root.val);
        node.left = root.left;
        node.right = root.right;
        return node;
    }
}
